package original;

/**
 * Created with IntelliJ IDEA.
 * ClassName: LinkedDemo
 * Package: original
 * Description:
 * User: fzykd
 *
 * @Author: LQH
 * Date: 2023-09-12
 * Time: 21:50
 */


class Node {
    public int data;
    public Node next;

    public Node(int data) {
        this.data = data;
    }
}

class MyLinkedNode {
    //节点的头引用
    private Node head;

    //创建链表
    public Node createLinked() {
        //创建节点
        Node node1 = new Node(10);
        Node node2 = new Node(20);
        Node node3 = new Node(30);
        Node node4 = new Node(40);
        Node node5 = new Node(50);
        Node node6 = new Node(60);
        //串联在一起
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        this.head = node1;

        return head;
    }

    //链表的遍历
    public void ergodic(String name, Node head) {
        //遍历要传入头节点
        //创建一个傀儡节点
        Node cur = head;

        System.out.print(name + ": ");
        while (cur != null) {
            System.out.print(cur.data + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    //判断元素是否存在
    public boolean contains(int key) {
        Node cur = head;
        while (cur != null) {
            if (cur.data == key) {
                return true;
            }

            cur = cur.next;
        }

        return false;
    }

    //头插法
    public Node addFirst(int data) {
        //new一个节点 直接插入
        Node node = new Node(data);
        node.next = this.head;
        this.head = node;

        return head;
    }

    //尾插法
    public void addLast(int data) {
        //判断有没有头节点 如果没有直接插入
        Node node = new Node(data);
        if (this.head == null) {
            this.head = node;
        } else {
            //如果有头节点 遍历到最后插入
            Node cur = this.head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = node;
        }
    }

    //任意位置插入
    public void addIndex(int index, int data) {

    }

    //反转链表
    public Node reverseList(Node head) {

        if (head == null) {
            return head;
        }

        Node prev = null;
        Node cur = head;

        while (cur != null) {
            Node curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }

        return prev;
    }

    //指定位置反转链表
    public Node reverseIndex(Node head, int m, int n) {

        Node dummy = new Node(-1);
        dummy.next = head;

        Node pre = dummy;
        for (int i = 1; i < m; i++) {
            pre = pre.next;
        }


        Node cur = pre.next;
        for (int i = 1; i < n - m + 1; i++) {
            Node temp = cur.next;
            cur.next = temp.next;

            temp.next = pre.next;
            pre.next = temp;
        }


        return dummy.next;
    }

}


public class LinkedDemo {
    public static void main(String[] args) {
        MyLinkedNode linkedNode = new MyLinkedNode();
        //创建链表
        Node head = linkedNode.createLinked();
//        //遍历节点
//        linkedNode.ergodic("遍历", head);
//        //判断元素是否存在
//        System.out.println(linkedNode.contains(10));
//        System.out.println(linkedNode.contains(11));
//
//        //头插法
//        Node node = linkedNode.addFirst(99);
//        linkedNode.ergodic("头插法", node);
//
//        linkedNode.addLast(100);
//        linkedNode.ergodic("尾插法", head);
//
//        Node node1 = linkedNode.reverseList(head);
//        linkedNode.ergodic("链表反转", node1);

        Node node2 = linkedNode.reverseIndex(head, 2, 5);
        linkedNode.ergodic("指定位置反转",node2);

    }
}



